package com.hjx.offer;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Optional;

/**
 * 重建二叉树
 *
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
 * 假设输入的前序遍历和中序遍历结果中不含重复的数字，例如输入前序遍历序列
 * {1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}， 则重建如下图所示的二叉树并输出它的头结点。
 *    1
 *   / \
 *  2   3
 * /   / \
 *4   5   6
 * \     /
 *  7   8
 */
class Offer_7 {

    public BinaryTreeNode<Integer> construct(int[] preOrder, int[] inOrder, int level) {
        if (preOrder == null || inOrder == null || preOrder.length == 0) {
            return null;
        }

        //1、前序遍历的第一个元素 为 根节点
        BinaryTreeNode<Integer> root = new BinaryTreeNode<>(preOrder[0]);
        root.setLevel(level++);

        //2、根据中序遍历的结果和根节点确定中序左子树\中序右子树元素集合
        int rootIndex = 0;
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == preOrder[0]) {
                rootIndex = i;
                break;
            }
        }

        int leftTreeLength = rootIndex;
        int[] leftTreeInOrder = new int[leftTreeLength];
        System.arraycopy(inOrder, 0, leftTreeInOrder, 0, leftTreeLength);

        int rightTreeLength = inOrder.length - 1 - rootIndex;
        int[] rightTreeInOrder = new int[rightTreeLength];
        System.arraycopy(inOrder, rootIndex + 1, rightTreeInOrder, 0, rightTreeLength);

        //3、根据中序遍历的左子树右子树结果 确定 前序遍历中的左子树和右子树集合
        int[] leftTreePreOrder = new int[leftTreeLength];
        System.arraycopy(preOrder, 1, leftTreePreOrder, 0, leftTreeLength);

        int[] rightTreePreOrder = new int[rightTreeLength];
        System.arraycopy(preOrder, 1 + leftTreeLength, rightTreePreOrder, 0, rightTreeLength);


        //4、递归构建二叉树左子树、右子树
        BinaryTreeNode<Integer> left = construct(leftTreePreOrder, leftTreeInOrder, level);
        root.setLeft(left);
        if (left != null) left.setParent(root);
        BinaryTreeNode<Integer> right = construct(rightTreePreOrder, rightTreeInOrder, level);
        root.setRight(right);
        if (right != null) right.setParent(root);

        //返回构造好的二叉树
        return root;
    }

    public static void main(String[] args) {

        // 所有结点都没有右子结点
        //            1
        //           /
        //          2
        //         /
        //        3
        //       /
        //      4
        //     /
        //    5
//        int[] preOrder = {1, 2, 3, 4, 5};
//        int[] inOrder = {5, 4, 3, 2, 1};

        // 普通二叉树
        //              1
        //           /     \
        //          2       3
        //         /       / \
        //        4       5   6
        //         \         /
        //          7       8
//        int[] preOrder = {1,2,4,7,3,5,6,8};
//        int[] inOrder = {4,7,2,1,5,3,8,6};

        // 所有结点都没有左子结点
        //            1
        //             \
        //              2
        //               \
        //                3
        //                 \
        //                  4
        //                   \
        //                    5
//        int[] preOrder = {1, 2, 3, 4, 5};
//        int[] inOrder = {1, 2, 3, 4, 5};
        // 完全二叉树
        //              1
        //           /     \
        //          2       3
        //         / \     / \
        //        4   5   6   7
        int[] preOrder = {1, 2, 4, 5, 3, 6, 7};
        int[] inOrder = {4, 2, 5, 1, 6, 3, 7};
//        int[] preOrder = null;
//        int[] inOrder = null;
        BinaryTreeNode<Integer> binaryTreeNode = new Offer_7().construct(preOrder, inOrder, 0);
        Optional<BinaryTreeNode<Integer>> option = Optional.ofNullable(binaryTreeNode);
        option.ifPresent(BinaryTreeNode::widthFirst);
    }
}


